#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>
#include <set>
#include <stack>
#include <algorithm>
#include <utility>

#ifndef __SOLVER_H__
#define __SOLVER_H__
#define MAX_WORD_SIZE 32

//#define __VERBOSE__	//Undefine if you don't want to get 'Solving...' sign


using namespace std;

namespace solver
{
    static const int range = 0x44f - 0x430 + 1;

	class Coords;

	typedef pair<wstring, deque<Coords> > WordStack;

	typedef vector<WordStack> Words;

    class TreeNode
    {
    public:
        TreeNode *next[range + 1];
        inline TreeNode()
        {
            memset(next, 0, sizeof(TreeNode *)*(range+1));
        }
        ~TreeNode();
    };

    class Tree
    {
        TreeNode *root;
    public:
        inline Tree()
        {
            root = new TreeNode;
        }
        inline ~Tree()
        {
            if (root) delete root;
        }

        void Insert(wchar_t *ptr);
        bool Find(wstring word);
        TreeNode *getRoot() { return root; }
    };

    class Coords
    {
    public:
        int x,y;
        Coords(int _x = 0, int _y = 0): x(_x), y(_y) {}
        inline bool operator != (const Coords &c)
        {
            return (c.x != x || c.y != y);
        }
        inline bool operator == (const Coords &c)
        {
            return (c.x == x && c.y == y);
        }
        inline int distance(int _x, int _y)
        {
            return abs(x - _x) + abs(y - _y);
        }
        inline Coords operator-(const Coords &c)
        {
            return Coords(x-c.x, y-c.y);
        }
    };

    class Field
    {
    	int w, h;
        wchar_t *f;
    public:
        inline Field(): w(0), h(0), f(NULL) {}
        inline Field(int _w, int _h): w(_w), h(_h)
        {
            f = new wchar_t [w*h];
            wchar_t *ptr = f;
            for( int i = w*h; i > 0; --i) *ptr++ = L' ';
        }

        explicit inline Field(const Field &fd)
        {
            w = fd.w;
            h = fd.h;
            f = new wchar_t [w*h];
            memcpy(f, fd.f, sizeof(wchar_t)*w*h);
        }

        inline ~Field()
        {
            if (f) delete f;
        }

        void Create(int _w, int _h)
        {
                if(f) delete f;
                f = new wchar_t [_w*_h];
                w = _w; h = _h;
                wchar_t *ptr = f;
                for( int i = w*h; i > 0; --i) *ptr++ = L' ';
        }

        inline wchar_t *operator[] (int y) const
        {
            return &f[y*w];
        }

        inline wchar_t &operator[] (const Coords &c) const
        {
            return (*this)[c.y][c.x];
        }
        
        inline const Field &operator= (const Field &fd)
        {
            if (f) delete f;
            w = fd.w;
            h = fd.h;
            f = new wchar_t [w*h];
            memcpy(f, fd.f, sizeof(wchar_t)*w*h);
            return fd;
        }

        void CreateMask(const Field &fd);

        inline int Width() const
        {
            return w;
        }

        inline int Height() const
        {
            return h;
        }

        inline bool isLinked(int x, int y)
        {
            if((x < w - 1 && (*this)[y][x + 1] != L' ') ||
               (x > 0 && (*this)[y][x - 1] != L' ') ||
               (y > 0 && (*this)[y - 1][x] != L' ') ||
               (y < h - 1 && (*this)[y + 1][x] != L' '))
                return true;
            return false;
        }

        friend istream &operator >> (istream &stream, const Field &f);
        friend ostream &operator << (ostream &stream, const Field &f);
    };

    void FindAllWords(const Field &f, Words &result);

    inline bool strlen_comp(const wstring &str1, const wstring &str2)
    {
        return str1.length() < str2.length();
    }

    bool ReadDictionary(const char *name);

    void getWords(vector<wstring> &words, int len);

    bool searchDict(const wstring &str);
};

#endif
